package main

import (
	"fmt"
	"math"
)

/**
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

子数组的最大值等于以各元素结尾的所有数组的最大值
我们定义以位置i结尾的最大的序列值为maxToCurrent，全部连续序列中最大的值为max，即
max = Max(maxToCurrent(0),maxToCurrent(1)...maxToCurrent(n-1))
maxToCurrent(n) = Max(maxToCurrent(n-1)+num[n],num[n]),我们知晓maxTocurrnet(0),那么便可依次递推到maxToCurrent(n)


*/

func main() {
	fmt.Println(maxSubArray([]int{-2, 1}))
}

func maxSubArray(nums []int) int {
	if len(nums) == 1 {
		return nums[0]
	}

	max := nums[0]
	maxToCurrent := nums[0]

	for i := 1; i < len(nums); i++ {
		maxToCurrent = int(math.Max(float64(maxToCurrent+nums[i]), float64(nums[i])))
		max = int(math.Max(float64(max), float64(maxToCurrent)))
	}

	return max
}
